package com.oocl.myHomework.list;

import java.util.Comparator;



public class DoubleLinkedList<T extends Object> {
	 class Node<T> {
		   public Node<T> pre;
		   public Node<T> next;
		   public T data;
		   
		   public Node(Node<T> pre,Node<T> next,T data){
			   this.pre = pre;
			   this.next = next;
			   this.data = data;
		   }
		}
	
	
	
     private int size = 0;
     public Node<T> header = new Node<T>(null,null,null);
     public Node<T> pointer = new Node<T>(null,null,null);
     
     public DoubleLinkedList(){
    	 this.header.pre = this.header.next = header;
     }
     public DoubleLinkedList(T[] array){
    	 this();
    	 this.size = array.length;
    	 addAll(array);
     }
     
     private void addAll(T[] array) {
		// TODO Auto-generated method stub
    	Node<T> cur = header;
		for(int i=0;i<array.length;i++){
			Node<T> newOne  = new Node<T>(cur,null,array[i]);
			if(i==array.length-1){
				this.pointer = cur;
			}
			cur.next = newOne ;
			cur = cur.next ;
		}
	}
     
     
     public  void addAtHead(T data){
    	 Node<T> next = header.next;
    	 Node<T> nn = new Node<T>(header,null,data);
    	 if(next ==null){
    		 header.next = nn;
    		 this.pointer = nn;
    	 }else{
    		 
    		 header.next = nn;
    		 next.pre = nn;
    	 }
    	 size++;
    	 
     }
     
     public void addAtEnd(T data) throws Exception{
    	 Node<T> endNode = getNodeByIndex(size-1);
    	 Node<T> nn = new Node<T>(endNode,null,data);
    	 endNode.next = nn;
    	 this.pointer = nn;
    	 size++;
     }
     
     public void add(T data,int index) throws Exception{
    	 if(index==0){
    		 addAtHead(data);
    	 }else if(index==size-1){
    		 addAtEnd(data);
    	 }else{
    	   Node<T> pre = getNodeByIndex(index-1);
    	   Node<T> next = pre.next;
    	   Node<T> cur = new Node<T>(pre,next,data);
    	   pre.next = cur;
    	   next.pre = cur;
    	   size++;
    	 }
     }
     
     public void delete(T data){
    	 int index = IndexOf(data);
    	 Node<T> cur = header;
    	 for(int i=0 ;i<=index;i++ )
    		 cur = cur.next;
    	 Node<T> pre = cur.pre;
    	 if(index==size-1){
    		 this.pointer = pre ;
    	 }
    	 Node<T> next = cur.next;
    	 if(next==null){
    		 pre.next = null;
    	 }else{
    		 pre.next = next;
    		 next.pre = pre;
    	 }
    	 size--;
     }
     
    public void update(T data,int index) throws Exception{
    	Node<T> nn =  getNodeByIndex(index);
    	nn.data = data;
    }
     
     
     private Node<T> getNodeByIndex(int index) throws Exception{
    	 if(index>=size) throw new  Exception("out of size");
    	 Node<T> cur = header;
    	 for(int i=0 ;i<=index;i++ )
    		 cur = cur.next;
    	 return cur;
     }
     
   
     
     public int IndexOf(T data){
    	 int index = -1;
    	 Node<T> temp = header.next;
    	   for(int i =0 ;i<size;i++){
    		   if(temp.data.equals(data) ){
    			   index = i; 
    			   break;
    		   }
    		   temp = temp.next;
    	   }
    	 return index;
    	 
     }
     
	public int getSize(){
    	 return size;
     }
	public T getElementByIndex(int i) throws Exception {
		// TODO Auto-generated method stub
		return getNodeByIndex(i).data;
	}
	
	
//	public void sort(){
//		for(int i=0;i<size;i++){
//			Node pre = header.next;
//			for(int j=0;j<size-1-i;j++){
//				if(pre.data>pre.next.data){
//					int temp = pre.data;
//					pre.data = pre.next.data;
//					pre.next.data = temp;
//				}
//				pre=pre.next;
//			}
//		}
//	}
//	
//	
//	public int binarySearch(int data) throws Exception{
//		
//		int index = -1;
//		int low = 0;
//		int high = size-1;
//		while(low<=high){
//			int mid = (low +high)/2;
//			if(data==getNodeByIndex(mid).data){
//				index = mid;
//				break;
//			}
//			if(data>getNodeByIndex(mid).data){
//				low = mid+1;
//			}
//			if(data<getNodeByIndex(mid).data){
//				high = mid-1;
//			}
//		}
		
//		return index;
///	}
	
	
	
//	public static void main(String[] args) throws Exception {
//		
//		int[] aa = {4,1,3,2,5};
//		DoubleLinkedList ll = new DoubleLinkedList(aa);
//		Node temp = ll.header.next;
//		System.out.println(ll.getSize());
//		for(int i=0;i<ll.getSize();i++){
//		    System.out.print(temp.data+" ");
//		    temp = temp.next;
//		}
//		System.out.println("");
//		System.out.println(ll.binarySearch(3));
//		System.out.println("");
//		System.out.println(ll.getSize());
//		Node temp1 = ll.header.next;
//		for(int i=0;i<ll.getSize();i++){
//		    System.out.print(temp1.data+" ");
//		    temp1 = temp1.next;
//		}
//	}
}
